typedef int datatype;
typedef struct avlnode
{
    datatype data;                   //数据元素
    int bf;                          //平衡因子
    struct avlnode *lchild, *rchild; //左右孩子指针
} AVLNode, *AVLTree;

void LL_rotate(AVLNode **p)
{
    //对*p为根的子树，做LL处理，处理之后，p指向的结点为子树的新根
    AVLNode *lp;
    lp = (*p)->lchild;
    (*p)->lchild = lp->rchild;
    lp->rchild = *p;
    *p = lp;
    (*p)->bf = 0;
    (*p)->rchild->bf = 0;
}
void RR_rotate(AVLNode **P)
{
    //对*p为根的子树，做RR处理，处理之后，p指向的结点为子树的新根
    AVLNode *rp;
    rp = (*p)->rchild;
    (*p)->rchild = rp->lchild;
    rp->lchild = *p;
    *p = rp;
    (*p)->bf = 0;
    (*p)->lchild->bf = 0;
}
void LR_rotate(AVLNode **p)
{
    //对*p为根的子树，做LR处理，处理之后，p指向的结点为子树的新根
    AVLNode *lp, *rlp;
    int r;
    lp = (*p)->lchild;
    rlp = lp->rchild;
    if (rlp->bf == 1)
        r = 1;
    else
        r = 2;
    RR_rotate(&((*p)->lchild));
    LL_rotate(p);
    if (r == 1)
    {
        (*p)->lchild->bf = 0;
        (*p)->rchild->bf = 1;
    }
    else
    {
        (*p)->lchild->bf = 1;
        (*p)->rchild->bf = 0;
    }
    (*p)->bf=0;
}

vodi RL_rotate(AVLNode **p){
    //对*p为根的子树，做RL处理，处理之后，p指向的结点为子树的新根
    AVLNode *rp,*lrp;
    int r;
    rp=(*p)->rchild;
    lrp=rp->lchild;
    if(lrp->bf=1)r=1;
    else r=2;
    LL_rotate(&((*p)->rchild));
    RR_rotate(p);
    if (r == 1)
    {
        (*p)->lchild->bf = 0;
        (*p)->rchild->bf =-1;
    }
    else
    {
        (*p)->lchild->bf = 1;
        (*p)->rchild->bf = 0;
    }
    (*p)->bf = 0;
}